package tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

import graph.Vertex;

/**
 * @uml.dependency   supplier="tree.Node"
 */
public class Tree {
	/**
	 * @uml.property  name="root"
	 * @uml.associationEnd  multiplicity="(1 1)"
	 */
	Node root = null;
	/**
	 * @uml.property  name="children"
	 * @uml.associationEnd  multiplicity="(0 -1)" elementType="tree.Tree"
	 */
	List<Tree> children;
	
	/**
	 * Parent of the tree, null if it's the root
	 */
	Tree parent;
	
	public Tree(Node root){
		this.root = root;
		this.children = new ArrayList<Tree>();
	}

	public Tree(Tree parent, Node root){
		this.root = root;
		this.parent = parent;
		this.children = new ArrayList<Tree>();
	}

	
	public void addChild(Tree t){
		this.children.add(t);
	}
	
	/**
	 * @return
	 * @uml.property  name="root"
	 */
	public Node getRoot(){
		return this.root;
	}
	
	public Tree getParent(){
		return this.parent;
	}
	
	public List<Tree> getChildren(){
		return this.children;
	}
	
	public Tree search(List<Vertex> elements){
		Tree res = null;
		if (this.root.elements.containsAll(elements))
			return this;
		
		for (Tree t : children){
			res = t.search(elements);
				break;
		}
		return res;
	}
	
	@Override
	public String toString(){
		return this.root.printElements() + 
				System.getProperty("line.separator") + 
				(this.children.size() > 0 ? this.children.toString() : "");
	}
	
	/**
	 * Find a bag for a given label
	 * @param bag
	 * @return
	 */
	public Tree findBags(String[] bag){
		return checkBags(bag, this);
	}
	
	/**
	 * Find a bag for a given vertex
	 * @param v
	 * @return
	 */
	public Tree findBags(Vertex v){
		Tree r=null;
			if(Arrays.deepToString(root.label).contains(String.valueOf(v.getName())))
				r = this;
			
			for (Tree t : this.children) {
				r = t.findBags(v);
				if(r!=null)
					return r;
			}
			
			return (r==null)?this:r;
	}
	
	/**
	 * 
	 * @param bag
	 * @param t
	 * @return
	 */
	public Tree checkBags(String[] bag, Tree t){
		Tree check=this;
		if(!bagContain(bag, t.root)){
			for (Tree tc : t.children) {
				if(bagContain(bag, tc.root))
					return tc;
				else
					check = checkBags(bag, tc);
			}
		}
		return check;
	}
	
	/**
	 * 
	 * @param bag
	 * @param n
	 * @return
	 */
	private boolean bagContain(String[] bag, Node n){
		int matchM = bag.length;
		int matchA = 0;
		for (int i = 0; i < bag.length; i++) {
			for (int j = 0; j < n.label.length; j++) {
				if(bag[i].endsWith(n.label[j])){
					matchA++;
					break;
				}
			}
		if(matchM <= matchA)
			return true;;
		}
	return false;
	}
	
	public Stack<Tree> findPathFromRoot(Tree v, Stack<Tree> l){
		for (Tree c : v.children) {
			if(c.getRoot().equals(v.getRoot())){
				l.add(this);
				return l;
			}
			l=c.findPathFromRoot(c, l);
		}
		return l;
	}
	
	public Tree lowestComAnc(Tree u, Tree v){
		Stack<Tree> lu, lv;
		lu = findPathFromRoot(u, new Stack<Tree>());
		lv = findPathFromRoot(v, new Stack<Tree>());
		
		
		Tree pathu,pathv, pathtmp = null;
		
		while(!lu.empty() || !lv.empty()){
			pathu=lu.pop();
			pathv=lv.pop();
			
			
			
			if(pathu==pathv)
				pathtmp=pathu;
			else{
				return pathtmp;
			}
		}
		
		return null;
	}
	
	/**
	 * 
	 * @param l
	 * @param t
	 * @return
	 */
	private List<Tree> setVerticeReachable(List<Tree> l, Tree t){
		if(!l.contains(t))
			l.add(t);
		for (Tree tree : t.getChildren()) {
			l = setVerticeReachable(l, tree);
		}
		return l;
	}
	
	/**
	 * 
	 * @param u
	 * @param v
	 * @return
	 */
	public boolean reachable(Vertex u, Vertex v){
		Tree p,cu,cv;
		Tree rootU = cu = findBags(u);
		Tree rootV = cv = findBags(v);
		
		List<Tree> ru = new ArrayList<Tree>(), rv = new ArrayList<Tree>(), rtmp = new ArrayList<Tree>();
		
		Tree lowestAnc = lowestComAnc(rootU, rootV);
		
		
		while(cu.getParent() != lowestAnc){
			p = cu.getParent();
			
			if(!ru.contains(p))
				ru.add(p);
			if(!ru.contains(cu));
				ru.add(cu);
			rtmp = new ArrayList<Tree>(ru);
			for (Tree tree : rtmp) {
				ru = setVerticeReachable(ru, tree);
			}
			cu = p;
		}
		
		while(cv.getParent() != lowestAnc){
			p = cv.getParent();
			
			if(!rv.contains(p))
				rv.add(p);
			if(!rv.contains(cv));
				rv.add(cv);
			rtmp = new ArrayList<Tree>(rv);
			for (Tree tree : rtmp) {
				rv = setVerticeReachable(rv, tree);
			}
			cv=p;	
		}
		return (ru.contains(cv) && rv.contains(cu));
	}
}
